package algorithm;

import util.ListNode;

/**
 * Description:
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
 * @author: chengrongkai
 * Date: 2021/3/8
 */
public class Solution12 {

    public static void main(String[] args) {
        int[] nums = {1,3,5,7,9};
        ListNode node1 = ListNode.getListNode(nums);
        int[] nums1 = {2,5,8,9,11};
        ListNode node2 = ListNode.getListNode(nums1);
        ListNode listNode = solution(node1,node2);
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }


    /**
     * 借助额外的哨兵节点，遍历两个链表，比较大小，谁比较小，就将哨兵节点的next指针指向它
     * @param node1
     * @param node2
     * @return
     */
    public static ListNode solution(ListNode node1,ListNode node2){
        ListNode node = new ListNode(0);
        ListNode pre = node;
        while (node1 != null && node2 != null){
            if (node1.val < node2.val){
                node.next = node1;
                node1 = node1.next;
            }else{
                node.next = node2;
                node2 = node2.next;
            }
            node = node.next;
        }
        if (node1 != null){
            node.next = node1;
        }
        if (node2 != null){
            node.next = node2;
        }
        return pre.next;
    }
}
